Corelab Seminar
2019-2020
Βασίλειος Νάκος
Γρηγορότεροι Αλγόριθμοι για το Άθροισμα Υποσυνόλου
Abstract.
Στο πρόβλημα του Αθροίσματος Υποσυνόλου δίνεται ένα σύνολο Χ με ν στοιχεία και ένας αριθμός t και σκοπός είναι να βρούμε αν υπάρχει υποσύνολο του Χ που αθροίζει στο t. Ο γρηγορότερος αλγόριθμος ανήκει στον Bringmann (SODA 17) και τρέχει σε χρόνο ~O(n +t). Αυτός ο αλγόριθμος είναι βέλτιστος ως προς τις παραμέτρους n,t αν υποθέσουμε ευρέως πιστευτές εικασίες στην θεωρία Πολυπλοκότητας. Από την άλλη, ο κλασικός αλγόριθμος του Bellman τρέχει σε χρόνο n * |S(X,t)|, όπου S(X,t) είναι το πλήθος όλων των αριθμών <= t που μπορούν να φτιαχτούν χρησιμοποιώντας κάποιο υποσύνολο του X. Και οι δύο αλγόριθμοι παράγουν όλο το σύνολο S(X,t), ενώ έχουν μη συγκρίσιμους χρόνους εκτέλεσης. Θα συζητήσουμε μία προσέγγιση που οδηγεί σε δύο νέους αλγόριθμους για το Άθροισμα Υποσυνόλου: έναν που μπορεί να απαντήσει αν το t ανήκει στο S(X,t) σε χρόνο ~ S(X,t), και έναν που παράγει όλο το |S(X,t)| σε χρόνο |S(X,t)|4/3. Η προσέγγισή μας βασίζεται σε μια αναγωγή του προβλήματος σε ένα πρόβλημα πολλαπλασιασμού αραιών πολυωνύμων, για το οποίο δίνουμε βελτιωμένα αποτελέσματα χρησιμοποιώντας τον Γρήγορο Μετασχηματισμό Φουριέ και μία τεχνική του Imre Ruzsa από την Αθροιστική Συνδυαστική.
Κοινή δουλειά με Karl Bringmann. Θα εμφανιστεί στο STOC 2020.